2019字节跳动Byte Camp夏令营算法笔试题--01.立方体塔

题目描述

时间限制：C/C++ 5秒，其他语言 10秒
空间限制：C/C++ 32768K，其他语言 65536K64bit
IO Format: %lld
本题可使用本地IDE编码，不做跳出限制，编码后请点击“保存并调试”按钮进行代码提交。
题目描述

小方有w个白色立方体和b个黑色立方体，现在小方想把它们堆成一个立方体塔。
一座高度为h的立方体塔，最底层有h个立方体，每往上一层，所需立方体减一，直到最高层，只需要1个立方体。
为了让这座塔看起来比较美观，小方希望，每一层都只能用一种颜色的立方体。
小方希望把这座塔叠得尽可能高，因此他想知道，塔的最大高度是多少，以及这个高度的立方体塔能有几种。
两种立方体塔，当且仅当至少有一层的颜色是不同的，被认为是不同的。
输入描述:

包含两个数字，w、b，代表有白色立方体w个、黑色立方体b个。

对于10%的数据: 0 <= w,b <= 200

对于20%的数据: 0 <= w,b <= 5000

对于100%的数据: 0 <= w,b <= 10^5

数据保证w+b >= 1输出描述:

包含两个数字，h、c，代表塔最高高度为h，有c种不同的此高度的塔。

由于塔的种类有可能很多，请将塔的种类数c对1000000007(10^9+7)取模。

示例1输入输出示例仅供调试，后台判题数据一般不包含示例

输入

1 1

输出

1 2

示例2输入输出示例仅供调试，后台判题数据一般不包含示例

输入

4 6

输出

4 2
说明
两组高度为4的塔的颜色从底到顶分别为：白黑黑黑，黑白黑白。

解题思路

1、先计算出立方体塔的最大高度；
2、回溯算法（此题是用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束）；

import java.util.Scanner;

public class Main {
	public static long count =0;
	public static int h;
	public static int a;
	public static int b;
	public static int sum;
	public static int[] visit;//1代表已访问，0代表未访问
	public static int[] arr;//1 代表白色，2代表黑色


	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long tt = 1000000007;
        a = in.nextInt();//白色
        b = in.nextInt();//黑色
        int min = a>b?b:a;
        sum = a+b;
        for(int i=min;i>0;i--) {
        	int temp = (1+i)*i/2;
        	if(sum>=temp) {
        		h = i;
        		break;
        	}
        }
        visit = new int[h+1];
        arr = new int[h+1];
        dfs(1);
		//取模 和取余 在被除数和除数符号相同时，没有区别  
        System.out.println(h+" "+ count%tt);       
	}
	
	public static void dfs(int layer) {
		if(layer > h) {
			if(check()) {
				count++;
			}
			return ;
		}
		for(int i=1;i<=2;i++) {
			if(visit[layer] == 0) {
				visit[layer] = 1;
				arr[layer] = i;
				dfs(layer+1);
				visit[layer] = 0;//回溯
			}
	        
		}
	}
	
	/*
	 * 检验
	 * 每一个立方体塔是否符合已知条件
	 */
	public static Boolean check() {
		int white = 0;
		int black = 0;
		for(int i=1;i<=h;i++) {
			if(arr[i] == 1) {
				white+=i;
			}else if(arr[i] == 2) {
				black+=i;
			}
		}
		if(white<=a && black<=b) {
			return true;
		}
		return false;
	}

}

结果

执行结果通过测试用例10%，目前不知道问题出现在哪，欢迎各位提出宝贵意见！